package algorithms;

public class Problem63 {
	public static void main(String[] args){
		int[][] obstacleGrid= {{0}};
		int num = uniquePathsWithObstacles(obstacleGrid);
		System.out.println(num);
	}
	
	public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
       int rowLen = obstacleGrid.length;
       int columnLen = obstacleGrid[0].length;
       int[][] result = new int[rowLen][columnLen];
       if(obstacleGrid[rowLen-1][columnLen-1] == 1)
    	   return 0;
       result[rowLen-1][columnLen-1] = 1;
       for(int row = rowLen-2; row >= 0; row--){
    	   if(obstacleGrid[row][columnLen-1] == 1)
    		   result[row][columnLen-1] = 0;
    	   else
    		   result[row][columnLen-1] = result[row+1][columnLen-1];
       }
       for(int column = columnLen-2; column >= 0; column --){
    	   if(obstacleGrid[rowLen-1][column] == 1)
    		   result[rowLen-1][column] = 0;
    	   else
    		   result[rowLen-1][column] = result[rowLen-1][column+1];
       }
       for(int row = rowLen-2; row >= 0; row--){
    	   for(int column = columnLen-2; column >= 0; column--){
    		   if(obstacleGrid[row][column] == 1)
    			   result[row][column] = 0;
    		   else
    			   result[row][column] = result[row+1][column] + result[row][column+1];
    	   }
       }
       return result[0][0];
    }
}
